#ifndef _TREENODE_H_
#define _TREENODE_H_
#include <cstring>
#include "Common.h"

namespace DataStructuresWet1
{

template <typename DataT>
class _TreeNode
{
public:
	friend class _TreeNode<DataT>;
	typedef enum
	{
		IS_LEFT_CHILD		= 0,
		IS_RIGHT_CHILD		= 1,
		IS_ORPHAN			= 2
	}TreeNodeParentage;

	typedef enum
	{
		LEAF				= 0,
		HAS_LEFT_CHILD		= 1,
		HAS_RIGHT_CHILD		= 2,
		HAS_TWO_CHILDREN	= 3
	}TreeNodeChildrenType;

	typedef enum
	{
		LEFT_CHILD = 0,
		RIGHT_CHILD = 1
	}TREE_CHILD_TYPE;

	_TreeNode									(DataT*				dataPtr, 
												_TreeNode<DataT>*	parent			= NULL, 
												_TreeNode<DataT>*	leftChild		= NULL, 
												_TreeNode<DataT>*	rightChild		= NULL,
												bool				setSiblings		= true);
	_TreeNode									(const _TreeNode& other);
	TreeNodeParentage		NodeParentage		() const;
	TreeNodeChildrenType	NodeChildrenType	() const;
	_TreeNode<DataT>*		GetParent			() const;
	_TreeNode<DataT>*		GetLeftChild		() const;
	_TreeNode<DataT>*		GetRightChild		() const;
	_TreeNode<DataT>*		GetLeftSibling		() const;
	_TreeNode<DataT>*		GetRightSibling		() const;
	DataT* const			GetDataPtr			() const;
	int						GetSize				() const;
	int						GetWeight			() const;
	int						GetHeight			() const;
	int						GetBalanceFactor	() const;
	//friend void				SetParent			(_TreeNode<DataT>* value,
	//											TREE_CHILD_TYPE childType,
	//											bool isUpdateSibling);
	void					SwitchPosition		(_TreeNode<DataT>& other);
	void					ReplaceParent		();
	void					MakeOrphan			();
	void					SetLeftChild		(_TreeNode<DataT>* value);
	void					SetRightChild		(_TreeNode<DataT>* value);
	void					SetLeftSibling		(_TreeNode<DataT>* value);
	void					SetRightSibling		(_TreeNode<DataT>* value);
	void					SetData				(DataT* data);
	_TreeNode<DataT>*		GetLeftMostChild	() const;
	_TreeNode<DataT>*		GetRightMostChild	() const;
	void					RotateRR			();
	void					RotateRL			();
	void					RotateLL			();
	void					RotateLR			();
	void					UpdateSize			();
	void					UpdateHeight		();
	void					UpdateWeight		();
protected:
	void					UpdateSiblings		();
	void					RotateLeft			();
	void					RotateRight			();
	void					Replace				(_TreeNode<DataT>& other);
	_TreeNode<DataT>*		Parent;
	_TreeNode<DataT>*		LeftChild;
	_TreeNode<DataT>*		RightChild;
	_TreeNode<DataT>*		LeftSibling;
	_TreeNode<DataT>*		RightSibling;
	DataT*					DataPtr;
	int						Size;
	int						Height;
	int						Weight;

};

//_TreeNode Implementation
template <typename DataT>
_TreeNode<DataT>::_TreeNode(
	DataT*				dataPtr, 
	_TreeNode<DataT>*	parent, 
	_TreeNode<DataT>*	leftChild, 
	_TreeNode<DataT>*	rightChild,
	bool				setSiblings) : 
	DataPtr(dataPtr), 
	Parent(parent), 
	LeftChild(leftChild), 
	RightChild(rightChild)
{
	if (setSiblings)
	{
		UpdateSiblings();
	}
	UpdateSize();
	UpdateHeight();
	UpdateWeight();
}

template <typename DataT>
_TreeNode<DataT>::_TreeNode(const _TreeNode& other) : 
	DataPtr(other.DataPtr), 
	Parent(other.Parent), 
	LeftChild(other.LeftChild), 
	RightChild(other.RightChild),
	LeftSibling(other.LeftSibling),
	RightSibling(other.RightSibling),
	Size(other.Size),
	Height(other.Height),
	Weight(other.Weight) {}

template <typename DataT>
typename _TreeNode<DataT>::TreeNodeParentage _TreeNode<DataT>::NodeParentage()  const
{
	if (!this->Parent)
	{
		return IS_ORPHAN;
	}
	if (this->Parent->LeftChild == this)
	{
		return IS_LEFT_CHILD;
	}
	if (this->Parent->RightChild == this)
	{
		return IS_LEFT_CHILD;
	}

	throw FailureException();
}

template <typename DataT>
typename _TreeNode<DataT>::TreeNodeChildrenType _TreeNode<DataT>::NodeChildrenType()  const
{
	if (!this->LeftChild && !this->RightChild)
	{
		return LEAF;
	}
	if (this->LeftChild != NULL && this->RightChild != NULL)
	{
		return HAS_TWO_CHILDREN;
	}
	if (this->LeftChild)
	{
		return HAS_LEFT_CHILD;
	}
	return HAS_RIGHT_CHILD;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetParent			()  const
{
	return this->Parent;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetLeftChild		()  const
{
	return this->LeftChild;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetRightChild		()  const
{
	return this->RightChild;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetLeftSibling		()  const
{
	return this->LeftSibling;
}

template <typename DataT>
_TreeNode<DataT>*	_TreeNode<DataT>::GetRightSibling	()  const
{
	return this->RightSibling;
}

template <typename DataT>
DataT* const		_TreeNode<DataT>::GetDataPtr			() const
{
	return this->DataPtr;
}

template <typename DataT>
int				_TreeNode<DataT>::GetSize					() const
{
	return this->Size;
}

template <typename DataT>
void			_TreeNode<DataT>::SetLeftChild		(_TreeNode<DataT>* value)
{
	this->LeftChild = value;
	if (value != NULL)
	{
		value->Parent = this;
		value->UpdateSiblings();
	}
	this->UpdateSize();
	this->UpdateHeight();
	this->UpdateWeight();
}

template <typename DataT>
void			_TreeNode<DataT>::SetRightChild		(_TreeNode<DataT>* value)
{
	this->RightChild = value;
	if (value != NULL)
	{
		value->Parent = this;
		value->UpdateSiblings();
	}
	this->UpdateSize();
	this->UpdateHeight();
}

template <typename DataT>
void				_TreeNode<DataT>::SetLeftSibling	(_TreeNode<DataT>* value)
{
	this->LeftSibling = value;

	if (value != NULL)
	{
		value->RightSibling = this;
	}
}

template <typename DataT>
void				_TreeNode<DataT>::SetRightSibling	(_TreeNode<DataT>* value)
{
	this->RightSibling = value;
	if (value != NULL)
	{
		value->LeftSibling = this;
	}
}

template <typename DataT>
void				_TreeNode<DataT>::UpdateSiblings		()
{
	switch (this->NodeParentage())
	{
	case IS_ORPHAN:
		this->RightSibling	= NULL;
		this->LeftSibling	= NULL;
		break;
	case IS_LEFT_CHILD:
		this->RightSibling	= this->Parent->RightChild;
		this->LeftSibling	= NULL;
		break;
	case IS_RIGHT_CHILD:
		this->RightSibling	= NULL;
		this->LeftSibling	= this->Parent->LeftChild;
		break;
	default:
		throw FailureException();
	}
}

template <typename DataT>
_TreeNode<DataT>*		_TreeNode<DataT>::GetLeftMostChild	() const
{
	_TreeNode<DataT>* node = const_cast<_TreeNode<DataT>*> (this); //this is okay, since we are not changing the state of this
	while(node->GetLeftChild() != NULL)
	{
		node = node->GetLeftChild();
	}
	return node;
}
template <typename DataT>
_TreeNode<DataT>*		_TreeNode<DataT>::GetRightMostChild	() const
{
	_TreeNode<DataT>* node = const_cast<_TreeNode<DataT>*> (this); //this is okay, since we are not changing the state of this
	while(node->GetRightChild() != NULL)
	{
		node = node->GetRightChild();
	}
	return node;
}

template <typename DataT>
void					_TreeNode<DataT>::RotateLeft		()
{
	_TreeNode<DataT>* tmp = this->RightChild;
	this->SetLeftChild(tmp->GetRightChild());
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(tmp);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(tmp);
		break;
	case IS_ORPHAN:
		tmp->MakeOrphan();
		break;
	}
	tmp->SetRightChild(this);

}
template <typename DataT>
void					_TreeNode<DataT>::RotateRight		()
{
	_TreeNode<DataT>* tmp = this->LeftChild;
	this->SetRightChild(tmp->GetLeftChild());
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(tmp);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(tmp);
		break;
	case IS_ORPHAN:
		tmp->MakeOrphan();
		break;
	}
	tmp->SetLeftChild(this);
}

template <typename DataT>
void					_TreeNode<DataT>::UpdateSize			()
{
	int leftChildSize = (this->LeftChild != NULL) ? this->LeftChild->GetSize() : 0;
	int rightChildSize = (this->RightChild != NULL) ? this->RightChild->GetSize() : 0;
	this->Size = leftChildSize + rightChildSize + 1;
}

template <typename DataT>
void					_TreeNode<DataT>::MakeOrphan			()
{
	switch (this->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->SetLeftChild(NULL);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->SetRightChild(NULL);
		break;
	case IS_ORPHAN:
		//do nothing
		break;
	}
	this->UpdateSiblings();
	this->Parent = NULL;
}

template <typename DataT>
void					_TreeNode<DataT>::RotateRR			()
{
	this->RotateLeft();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateRL			()
{
	this->RightChild->RotateRight();
	this->RotateLeft();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateLL			()
{
	this->RotateRight();
}
template <typename DataT>
void					_TreeNode<DataT>::RotateLR			()
{
	this->LeftChild->RotateLeft();
	this->RotateRight();
}

template <typename DataT>
void					_TreeNode<DataT>::UpdateHeight		()
{
	int leftChildHeight = (this->LeftChild != NULL) ? this->LeftChild->GetHeight() : 0;
	int rightChildHeight = (this->RightChild != NULL) ? this->RightChild->GetHeight() : 0;
	this->Height = MAX(leftChildHeight, rightChildHeight) + 1;
}

template <typename DataT>
void					_TreeNode<DataT>::UpdateWeight		()
{
	int childWeight = (this->LeftChild != NULL) ? this->LeftChild->GetWeight() : 0;
	this->Weight = childWeight + 1;
}

template <typename DataT>
int						_TreeNode<DataT>::GetHeight			() const
{
	return this->Height;
}

template <typename DataT>
int						_TreeNode<DataT>::GetWeight			() const
{
	return this->Weight;
}

template <typename DataT>
int						_TreeNode<DataT>::GetBalanceFactor	() const
{
	return this->LeftChild->GetHeight() - this->RightChild->GetHeight();
}

template <typename DataT>
void					_TreeNode<DataT>::SwitchPosition		(_TreeNode<DataT>& other)
{
	DataT* tmp = other.DataPtr;
	other.DataPtr = this->DataPtr;
	this->DataPtr = tmp;
}

template <typename DataT>
void					_TreeNode<DataT>::ReplaceParent			()
{
	if (this->Parent == NULL)
	{
		return;
	}
	switch(this->Parent->NodeParentage())
	{
	case IS_LEFT_CHILD:
		this->Parent->Parent->SetLeftChild(this);
		break;
	case IS_RIGHT_CHILD:
		this->Parent->Parent->SetRightChild(this);
		break;
	case IS_ORPHAN:
		this->Parent = NULL;
		break;
	}
	this->SetRightSibling(this->Parent->RightSibling);
	this->SetLeftSibling(this->Parent->LeftSibling);
	
}

template <typename DataT>
void				_TreeNode<DataT>::Replace					(_TreeNode<DataT>& other)
{
	switch(other.NodeParentage())
	{
		case IS_LEFT_CHILD:
			other.Parent->SetLeftChild(this);
			break;
		case IS_RIGHT_CHILD:
			other.Parent->SetRightChild(this);
			break;
		case IS_ORPHAN:
			this->Parent = NULL;
			break;
	}
	this->SetLeftChild(other.LeftChild);
	this->SetRightChild(other.RightChild);
	this->SetLeftSibling(other.LeftSibling);
	this->SetRightSibling(other.RightSibling);
	this->Size = other.Size;
	this->Height = other.Height;
}


}//DataStructuresWet1
#endif //_TREENODE_H_